package com.hdu.hot100.list;
import java.util.HashMap;
import java.util.Map;

public class lc146 {
    class LRUCache {

        Node head;
        Node tail;

        Map<Integer, Node> key2node = new HashMap<>();
        int capacity;

        public LRUCache(int capacity)
        {
            this.capacity = capacity;
            initHeadAndTail();
        }

        public int get(int key)
        {
            Node targetNode = key2node.get(key);
            if (targetNode == null)
            {
                return -1;
            }
            else
            {
                moveToHead(targetNode);
                return targetNode.val;
            }
        }

        public void put(int key, int value)
        {
            Node targetNode = key2node.get(key);
            if (targetNode == null)
            {
                if (capacity == key2node.size())
                {
                    Node lastNode = tail.prev;
                    delNode(lastNode);
                    key2node.remove(lastNode.key);
                }
                Node newNode = new Node(key, value);
                addAsHead(newNode);
                key2node.put(key, newNode);
            }
            else
            {
                targetNode.val = value;
                moveToHead(targetNode);
            }
        }
        void initHeadAndTail()
        {
            head = new Node(0, 0);
            tail = new Node(0, 0);

            head.next = tail;
            tail.prev = head;
        }


        void moveToHead(Node node)
        {
            delNode(node);
            addAsHead(node);
        }

        void addAsHead(Node node)
        {
            Node second = head.next;

            node.next = second;
            second.prev = node;

            head.next = node;
            node.prev = head;
        }

        void delNode(Node node)
        {
            Node prev = node.prev;
            Node next = node.next;

            prev.next = next;
            next.prev = prev;
        }

        class Node
        {
            int key;
            int val;
            Node prev;
            Node next;

            public Node(int key, int val)
            {
                this.key = key;
                this.val = val;
            }
        }
    }


/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
}
